//冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。 
//
// 在加热器的加热半径范围内的每个房屋都可以获得供暖。 
//
// 现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。 
//
// 说明：所有供暖器都遵循你的半径标准，加热的半径也一样。 
//
// 
//
// 示例 1: 
//
// 
//输入: houses = [1,2,3], heaters = [2]
//输出: 1
//解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
// 
//
// 示例 2: 
//
// 
//输入: houses = [1,2,3,4], heaters = [1,4]
//输出: 1
//解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
// 
//
// 示例 3： 
//
// 
//输入：houses = [1,5], heaters = [2]
//输出：3
// 
//
// 
//
// 提示： 
//
// 
// 1 <= houses.length, heaters.length <= 3 * 104 
// 1 <= houses[i], heaters[i] <= 109 
// 
// Related Topics 数组 二分查找 排序 
// 👍 202 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        int ret = -1;
        List<Integer> heaterslist = Arrays.stream(heaters).boxed().collect(Collectors.toList());
//        List<Integer> list = new ArrayList<Integer>(Arrays.asList(heaters));
        heaterslist.sort((Integer left,Integer right) -> {
            return left - right;
        });
        for(int i=0; i<heaterslist.size(); i++){
            heaters[i] = heaterslist.get(i);
        }
        //找到离每个房间最近的供暖器
        for(int house : houses){
            //房子右边最近的供暖器
            int indexRight = binarySearch01(heaters,house);
            int distRight = indexRight == heaters.length ? Integer.MAX_VALUE : heaters[indexRight] - house ;
            //房子左边最近的供暖器
            int indexLeft = indexRight - 1;
            int distLeft = indexLeft <= -1 ? Integer.MAX_VALUE : house - heaters[indexLeft];
            int distMin = Math.min(distRight, distLeft);
//            System.out.println("house:"+house+", indexRight:"+indexRight+", idnexLeft:"+indexLeft+", distMin:"+distMin);
            ret = Math.max(ret, distMin);
        }
        return ret;
    }

    public int binarySearch01(int[] arr, int target){
//        System.out.println("arr:"+Arrays.toString(arr)+", target:"+target);
        int head = 0, tail = arr.length-1, mid;
        while(tail - head > 3){
            mid = head + ((tail - head) >> 1);
            if(arr[mid] >= target){
                tail = mid;
            }else{
                head = mid + 1;
            }
        }
        for(int i = head; i <= tail; i++){
            if(arr[i] >= target){
                return i;
            }
        }
        return arr.length;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
